/*
 * @Author: szx
 * @Date: 2021-11-05 11:23:56
 * @LastEditTime: 2021-11-05 13:52:20
 * @Description:
 * @FilePath: \leetcode\700-799\784\784.cpp
 */

#include <iostream>
#include <vector>
using namespace std;
// class Solution {
//    public:
//     vector<string> letterCasePermutation(string s) {
//         vector<string> res;
//         dfs(res, 0, s);
//         return res;
//     }
//     void dfs(vector<string> &res, int i, string s) {
//         if (i > s.length() - 1) {
//             res.emplace_back(s);
//             return;
//         }
//         dfs(res, i + 1, s);
//         if (s[i] <= 'z' && s[i] >= 'a') {
//             s[i] = s[i] + 'A' - 'a';
//         } else if (s[i] <= 'Z' && s[i] >= 'A') {
//             s[i] = s[i] - ('A' - 'a');
//         } else {
//             return;
//         }
//         dfs(res, i + 1, s);
//     }
// };
// class Solution {
//    public:
//     vector<string> letterCasePermutation(string s) {
//         vector<string> res;
//         dfs(res, 0, s);
//         return res;
//     }
//     void dfs(vector<string> &res, int cur, string s) {
//         for (int i = cur; i < s.length(); i++) {
//             cout << s << endl;

//             if (s[i] <= 'z' && s[i] >= 'a') {
//                 dfs(res, i + 1, s);
//                 s[i] = s[i] + 'A' - 'a';
//             } else if (s[i] <= 'Z' && s[i] >= 'A') {
//                 dfs(res, i + 1, s);
//                 s[i] = s[i] - ('A' - 'a');
//             }
//         }
//         res.emplace_back(s);
//     }
// };

#include <deque>
//还有一种迭代的思想
class Solution {
   public:
    vector<string> letterCasePermutation(string s) {
        deque<string> res;
        res.emplace_back(s);
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) continue;
            for (int j = res.size(); j > 0; --j) {
                auto sub = res.front();
                res.pop_front();
                res.emplace_back(sub);
                sub[i] ^= (1 << 5);
                res.emplace_back(sub);
            }
        }
        return vector<string>(res.begin(), res.end());
    }
};



int main() {
    Solution s;
    vector<string> res = s.letterCasePermutation("a1b1");
    for (string r : res) {
        cout << r << " ";
    }
    cout << endl;
    return 0;
}